#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-09-25 10:25 上午
# @Author  : yangdy
# @File    : 2020-09-25.106.从中序与后序遍历序列构造二叉树
# @Software: PyCharmCE
from tools.my_methods import *


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        if not inorder or not postorder:
            return None
        root = TreeNode(postorder[-1])
        i = inorder.index(root.val)
        # print(i)
        left = self.buildTree(inorder[:i], postorder[:i])
        right = self.buildTree(inorder[i+1:], postorder[i:-1])
        root.left = left
        root.right = right
        # display(root)
        return root


questions = [
    ([9, 3, 15, 20, 7], [9, 15, 7, 20, 3],),
]

work(questions, lambda q: Solution().buildTree(q[0], q[1]))
